package com.zhouyong.leetcode.两数相加2;

import com.google.common.collect.Lists;
import com.zhouyong.leetcode.ListNode;

import java.util.Collections;
import java.util.LinkedList;

/**
 * @Author 99
 * @Date 2022/10/12 11:12
 * @Version 1.0
 */
public class Test {

    // 给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。
    // 请你将两个数相加，并以相同形式返回一个表示和的链表。
    // 你可以假设除了数字 0 之外，这两个数都不会以 0开头。

    //示例1：
    //输入：l1 = [2,4,3], l2 = [5,6,4]
    //输出：[7,0,8]
    //解释：342 + 465 = 807.

    //示例 2：
    //输入：l1 = [0], l2 = [0]
    //输出：[0]

    //示例 3：
    //输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
    //输出：[8,9,9,9,0,0,0,1]

    public static void main(String[] args) {
        ListNode node = new ListNode(9, new ListNode(9, new ListNode(9, new ListNode(9, new ListNode(9, new ListNode(9, new ListNode(9)))))));
        ListNode node1 = new ListNode(9, new ListNode(9, new ListNode(9, new ListNode(9))));
        System.out.println(addTwoNumbers(node, node1));
    }

    public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {

        LinkedList<Integer> l1List = Lists.newLinkedList();
        LinkedList<Integer> l2List = Lists.newLinkedList();
        while (l1 != null) {
            l1List.add(l1.val);
            l1 = l1.next;
        }
        while (l2 != null) {
            l2List.add(l2.val);
            l2 = l2.next;
        }
        return l1List.size() > l2List.size() ? calculate(l1List, l2List) : calculate(l2List, l1List);
    }

    public static ListNode calculate(LinkedList<Integer> l1List, LinkedList<Integer> l2List) {
        int pos = 0, x = l1List.size() - 1, y = l2List.size() - 1;
        Collections.reverse(l1List);
        Collections.reverse(l2List);
        LinkedList<Integer> list = new LinkedList<>();
        ListNode newNode = null;
        while (x >= 0 || y >= 0 || pos == 0) {
            int a = x >= 0 ? l1List.get(x) : 0;
            int b = y >= 0 ? l2List.get(y) : 0;
            int num = a + b + pos;
            list.add(num % 10);
            pos = num / 10;
            x--;
            y--;
        }
        // 转成链表
        for (int i = list.size() - 1; i >= 0; i--) {
            newNode = new ListNode(list.get(i), newNode);
        }
        return newNode;
    }
}
